1. Field of the Invention
The present invention relates generally to computer systems having a memory and multiple processors with caches. In particular, the present invention relates to a system and method for maintaining cache coherence that is event driven and changes the state of the caches and memories based on the current memory state and a head of a list of corresponding cache entries.
2. Description of the Background Art
The use of multiple processors is a recent trend in computer design. The processors used in the multi-processor architectures generally each have a dedicated cache. A cache is a relatively small group, when compared to shared memories, of high speed memory cells that are specifically dedicated to a processor. A processor's cache may be on the processor chip itself or may be on separate chips.
Processors use caches to hold data that the processor has recently accessed. A memory access is any action, such as a read or a write, where a processor receives, modifies, or receives as well as modifies the contents of a memory location. Generally, a processor can access data in its cache faster than it can access data in the main memory of the computer. By using data in its cache, a processor does not use the bus of the computer system to access data. This leaves the bus free for use by other processors and devices.
A particular problem associated with the use of caches is that the data becomes "stale." A first processor may access data in the main memory and copy the data into its cache. The first processor may then modify the data in its cache. At the instant when the data in the cache of the first processor is modified, the corresponding data in the memory is stale. If a second processor subsequently accesses the original data in the main memory, the second processor does not find the most current version of the data. The most current version is in the cache of the first processor.
A prior art solution to this problem is for processors and caches to eavesdrop or snoop on the bus. When the first processor detects the main memory access by the second processor for data that the first processor holds in its cache, the first processor inhibits the main memory and supplies the data to the second processor. In this way, a processor always receives the most current version of the data. However, this prior art solution suffers from a number of problems. Computer architectures are moving to multiple-processor, multiple-bus configurations, and for efficiency purposes, many signals on a bus are not transmitted across the interface to other busses. Among signals, which are not transmitted across the interface, are memory access signals where the path between source and target devices does not cross the interface. When devices do not transmit all memory access signals over its data path, it is impossible for processors, which are not the source and target, to eavesdrop on memory accesses and therefore, impossible to determine when the data is stale. Furthermore, decreases in access time of main memories and increases in the size of caches have created other problems with eavesdropping. Processors, with large caches, cannot access the larger cache fast enough to make the prior art solution workable unless other memory accesses are delayed while eavesdropping is performed. Thus, for a number of reasons, this prior art solution is not effective.
A second prior art solution is to provide directory structures in memories. The directory structures are used to provide pointers to the locations storing the current versions of the data, and are often referred to as memory or cache tags. A memory tag is associated with a memory address or line whose data is held in a cache. Similarly, a cache tag is associated with a cache line and can indicate the cache line of another processor where the data is held. When a processor copies the data at that address into its cache, a memory tag is updated to identify the processor in whose cache the data is held. If a second processor attempts to access the data in the memory, the processor will receive the memory tag which redirects the second processor to fetch the data from the first processor cache. More specifically, each tag cell is more than one bit wide and contains data that indicates if the data held in the corresponding memory line is valid data or if a cache of a processor holds the data. The memory tags can indicate that there are multiple read-only copies of the memory line in the caches of other processors (this state is referred to as "FRESH"), or that there is a modifiable copy of the data in the memory line (this state is referred to as "OWNED"). Fresh data may also be referred to as "unowned" data. Cache tags operate in a similar manner. Thus, memory and cache tags remove the need for eavesdropping. However, one problem with existing directory structures and protocols for memory is that they are not optimized for the particular use or operation of the memory which can change over time. The fresh state is most efficient when data is only being read; and the owned state is most efficient when data is likely to be written. Therefore, existing directory structures for memory and cache do not provide an effective means for converting the memory state from fresh to owned and vice versa.
Therefore, there is a continuing need for a system and method for ensuring that processors receive fresh data and for converting between the states of fresh and owned. In other words, there is a need for a system and method for automatically washing (converting a memory state from owned to fresh) cache and memory lines.